use std::fmt;
use std::mem::MaybeUninit;

#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

impl<T> Clone for List<T> where T: Clone {
    fn clone(&self) -> Self {
        match self {
            &List::Cons(ref val, ref next) => {
                List::Cons(val.clone(), next.clone())
            },
            &List::Nil => List::Nil,
        }
    }
}

impl<T> List<T> {
    fn new() -> List<T> {
        List::Nil
    }

    fn len(&self) -> usize {
        self.iter().count()
    }

    fn push_front(&mut self, elem: T) {
        let mut mem = unsafe { MaybeUninit::zeroed().assume_init() };
        std::mem::swap(self, &mut mem);
        let mut mem = List::Cons(elem, Box::new(mem));
        std::mem::swap(self, &mut mem);
        std::mem::forget(mem);
    }

    fn push_back(&mut self, elem: T) {
        let mut curr = self;
        while let List::Cons(_, next) = curr {
            curr = next;
        };
        *curr = List::Cons(elem, Box::new(List::Nil));
    }
}
impl<T> List<T> {
    fn iter(&self) -> Iter<T> {
        Iter { list: self }
    }
}

struct Iter<'a, T> {
    list: &'a List<T>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.list {
            List::Cons(ref val, ref next) => {
                self.list = next;
                Some(val)
            },
            List::Nil => None,
        }
    }
}

// todo 求解Mutable的Iterator如何实现
//struct IterMut<'a, T> {
//    list: &'a mut List<T>,
//}
//
//impl<'a, T> Iterator for IterMut<'a, T> {
//    type Item = &'a mut T;
//
//    fn next(&mut self) -> Option<Self::Item> {
//        match self.list {
//            List::Cons(ref mut val, ref mut next) => {
//                self.list = next;
//                Some(val)
//            },
//            List::Nil => None,
//        }
//    }
//}

impl<T> fmt::Display for List<T> where T: fmt::Display {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "[ ")?;
        for item in self.iter() {
            write!(f, "{} ", item)?;
        };
        write!(f, "]")?;
        Ok(())
    }
}

#[test]
fn test_list() {
    let mut list = List::new();

    list.push_front(1);
    list.push_front(2);
    println!("{}", list);
    list.push_front(3);

    list.push_back(6);

    list.push_back(4);
    list.push_back(5);

    println!("linked list has length: {}", list.len());
    println!("{}", list);

    let mut list2 = list.clone();
    list2.push_back(123);
    println!("{}", list2);
    println!("{}", list);

    for item in list2.iter() {
        println!("item = {}", item);
    }
}
